package cn.suchan.jianzhi.q15_reverselist;

import java.util.ArrayList;
import java.util.List;

/**
 * 知识点：反转链表
 * 题目描述
 * 输入一个链表，反转链表后，输出新链表的表头。
 *
 * @author suchan
 * @date 2019/05/26
 */
public class Solution {

    /**
     * 借助List进行翻转
     *
     * @param head
     * @return
     */
    public ListNode ReverseList(ListNode head) {
        int count = 0;
        ListNode node = head;
        List<ListNode> list = new ArrayList<>();
        while (node != null) {
            count++;
            list.add(node);
            node = node.next;
        }
        if (count == 0) {
            return null;
        }
        for (int i = count - 1; i > 0; i--) {
            list.get(i).next = list.get(i - 1);
        }
        list.get(0).next = null;
        return list.get(count - 1);
    }

    /**
     * 直接翻转（非递归）
     *
     * @param head
     * @return
     */
    public ListNode ReverseList1(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode tempNode;
        ListNode newNode = null;

        while (head != null) {
            tempNode = head.next;
            head.next = newNode;
            newNode = head;
            head = tempNode;
        }

        return newNode;
    }

    /**
     * 直接翻转（递归）
     *
     * @param head
     * @return
     */
    public ListNode ReverseList2(ListNode head) {
        //链表为空直接返回，而head->next为空是递归基
        if (head == null || head.next == null) {
            return head;
        }
        //一直循环到链尾
        ListNode newList = ReverseList(head.next);
        //翻转链表的指向
        head.next.next = head;
        //记得赋值NULL，防止链表错乱
        head.next = null;
        //新链表头永远指向的是原链表的链尾
        return newList;
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        Solution solution = new Solution();
        ListNode node = solution.ReverseList1(node1);
        System.out.println(node.val);
    }
}
